package com.godpaper.util
{
	import com.godpaper.game.chess.twoHitOne.Board;
	import com.godpaper.game.chess.twoHitOne.Player;
	import com.godpaper.game.chess.twoHitOne.Winner;
	
	import de.polygonal.ds.Array2;
	
	/**
	 *
	 * This essay is a detailed explanation of one of the most important
	 *  data structures ever created for Game Artificial Intelligence. 
	 * The minimax tree is at the heart of almost every board game program in existence.
	 */	
	public class GameTrees
	{
		protected var winner:Winner;
		public function GameTrees()
		{
			//TODO: implement function
			winner = new Winner();
		}
		/**
    	 * if(game over in current board position)
         * return winner
         * children = all legal moves for player from this board
         * if(max's turn)
         * return maximal score of calling minimax on all the children
         * else (min's turn)
         * return minimal score of calling minimax on all the children
         * 
         * @param player the chess game player.
		 * @param board the chess game board.
		 * @return the winner of this game.
		 * 
		 */		
		public function MinMax(player:Player,board:Board):Winner
		{
			return winner;
		}
		
		public function MinMove():void{};
		public function MaxMove():void{};
		private var _positionEvaluation:Number;
		public function doEvaluation(position:Array2):Number
		{
			//Todo:
			return _positionEvaluation;
		};
		/**
		 * Search enhancements
		 * All techniques above aimed at reducing the number of nodes to search by better move ordering. 
		 * There is another class of enhancements with the same goal, but with different means. 
		 * These enhancements try to exploit the nature of the AlphaBeta algorithm, 
		 * which has to search fewer nodes when the alpha-beta window is smaller. 
		 */		
		
		 /**
		 * The normal MiniMax code is a bit clumsy, 
		 * since one side is trying to maximize the value and the other 
		 * is trying to minimize - therefore, 
		 * with MiniMax we always have to check if we are the side 
		 * trying to maximize or the side trying to minimize. 
		 * A neat way to get rid of this and to have a simpler function is NegaMax.
		 * With the NegaMax algorithm both sides try to maximize all the time.
		 * NegaMax is identical to MiniMax, it's just a nicer formulation.
		 * 
		 * @param postion the piece's postion in board.
		 * @param depth the piece's depth in this game tree.
		 * 
		 * @see http://www.fierz.ch/
		 */	
		 
		public function NegaMax(position:Array2,depth:int):void
		{
		
		}
		/**
		 * 
		 * The major improvement over MiniMax/NegaMax is the AlphaBeta algorithm: 
		 * Here you realize that you don't have to go through the whole search tree. 
		 * If you find one winning continuation, you don't have to look at any others. 
		 * Similarly, if you have found one continuation which will give you 
		 * the value V you can stop your search along another continuation 
		 * if you find only one possibility for your opponent 
		 * which gives you a lower score than V. 
		 * You don't have to look at all the other possibilities your opponent
		 *  might have - one refutation is enough! 
		 * Here is the code for AlphaBeta, extending the earlier NegaMax code: 
		 * It receives two extra parameters, alpha and beta. 
		 * They define an interval within which the evaluation has to be. 
		 * If it isn't, the function will return. 
		 * Your first call to AlphaBeta will be with an interval -INFINITY...INFINITY; 
		 * subsequent recursive calls to the function will make the window smaller. 
		 * 
		 * @param position the piece's postion in board.
		 * @param depth the piece's depth in this game tree.
		 * @param alpha INFINITY.
		 * @param beta -INFINITY.
		 * 
		 */		
		public function AlphaBeta(position:Array2,depth:int,alpha:int,beta:int):void
		{
		
		}
		
		/**
		 * Windowing is the simplest of the following techniques.
		 * In an iterative deepening framework, we always have a value of the previous iteration.
		 * Therefore, we try to reduce the search effort by using a smaller alpha-beta window. 
		 * Instead of using -INFINITY...+INFINITY we can use an interval lastvalue-WINDOW...lastvalue+WINDOW. 
		 * If the true MiniMax value at this iteration is really inside this window, 
		 * we will just need to search fewer nodes than with the larger window. 
		 * On the other hand, 
		 * our guess that the true value is inside this window might also be wrong. 
		 * In this case, we will get a fail-high or a fail-low. In this case, 
		 * we will have to do a re-search with a larger window. 
		 */		
		public function Windowing():void{}
		
		/**
		 * MTD(f) is another clever trick which uses AlphaBeta's property of returning boundaries on the true MiniMax value.
		 * MTD(f) makes a few calls to AlphaBeta with changing windows to get the true value of the position. 
		 * Each time it gets either a lower or an upper bound on the current position's value. 
		 * These bounds converge toward the true MiniMax value.
		 * @param position
		 * @param firstGuess
		 * @param depth
		 * 
		 */		
		public function MTDF(position:Array2,firstGuess:int,depth:int):void
		{
			
		}
		
		/**
		 * Principal variation searching 
		 * Windowing is simple and it is quite good. 
		 * However, windowing is restricted to the root node. 
		 * PVS tries to go a bit further by making assumptions on the alpha-beta window at every node. Here's the basic idea: Since we have gone to a lot of trouble with our move ordering schemes above, we can be pretty confident that we will find the best move early on. Therefore, our localalpha will be at its maximal value after the first few moves. PVS tries to exploit this by calling the next recursion of AlphaBeta with different parameters than standard-AlphaBeta. AlphaBeta would use alpha and beta. In PVS however, we already guess that our current localalpha will be better than what we will get with the remaining moves. Therefore we set alpha to localalpha and beta to localalpha+1, that is, we use a call 
		 * value=-alphabeta(p,d-1,-(localalpha+1),-localalpha);
		 * We expect this call to fail low, because we believe that we have already 
		 * found the best move. If this call does not fail low, 
		 * we need to revise our assumption and call AlphaBeta again 
		 * with the normal alpha and beta bounds.
		 * PVS is also often called NegaScout. 
		 * It gets its name from the scout search which a minimal window,
		 * which sort of probes the territory to see whether a real search is necessary. 
		 */		
		public function PVS():void{}
		
		/**
		 * Enhanced transposition cutoffs
		 * ETC is a cute idea: in a normal AlphaBeta search with a hashtable, 
		 * you will be searching through all possible moves, and for every move you make, 
		 * you do a hashtable lookup to see if you can return immediately. 
		 * ETC takes this idea one step further: Before doing your recursive AlphaBeta call, 
		 * you look up all possible successor positions of the current position. 
		 * If you get a hashtable hit on one of these calls which gives you a return value > beta, 
		 * you can immediately return without a search. 
		 * The reason ETC helps is that in the normal AlphaBeta case, 
		 * you generate a movelist, and let's assume that move number 5 would lead to a hashtable hit leading to a cutoff. 
		 * Nevertheless, in the normal AlphaBeta framework, 
		 * you will have to search through moves number 1 - 4, 
		 * and only then do you find that move number 5 gives you a cutoff. 
		 * This search is made unnecessary with the ETC lookup. 
		 * 
		 */		
		public function ETC():void{}
		
		/**
		 *Singular extensions 
		 * Singular extensions (SE) got their 15 minutes of fame when they were used by the Deep Blue team which won it's chess match against world champion Garry Kasparov.
		 * Since then, SE seems to have been abandoned by most. The idea of singular extensions is appealing, 
		 * and what makes it so appealing is that it is game-independent: Many ideas on how to improve tree search depend heavily on the game, and therefore lack generality. Singular extensions in theory work for all games. 
		 * As the name says, SE is about extensions. Up to now, I have avoided this topic, 
		 * but it is important: The AlphaBeta function I have shown searches a game tree to a fixed depth. 
		 * However, many lines of play are just stupid, while others are more interesting. 
		 * The aim of SE is to catch some of the more interesting lines, 
		 * and to search them deeper than the rest. It relies on detecting forced moves for one side, and on extending the search depth in the case of forced moves. Humans play chess like this, and can solve long variations which are forced easily. SE tries to emulate this behavior.
		 */		
		public function SE():void{}
		
		/**
		 *Quiescence search 
		 * As I just said above, the basic search algorithm I presented always goes to a fixed depth. 
		 * However, it may often not be a good idea to evaluate a position if it is too chaotic. 
		 * Exactly what too chaotic might mean depends on the game. 
		 * A simple example in chess is a position where white to move is a rook down but can promote a pawn to a queen, 
		 * winning the game. If we were to call our static evaluation function in this position, 
		 * it would (unless it was smart, which evaluation functions usually aren't) conclude that white is dead lost, 
		 * a rook down. Therefore, a technique called quiescence search is often used: Once you want to call your evaluation function, 
		 * you take a look at very few select moves that need to be checked further. You have to make sure that you are very restrictive in your quiescence search, 
		 * otherwise your search tree will explode completely. 
		 */		
		public function QS():void{}
		
		/**
		 *Depth reductions 
		 * Pruning in general is a way of deciding to reduce the search depth of the current line. 
		 * There are many ways in which you can do this, and some of them are game specific (see below). 
		 * Others are of a more general nature. The whole idea comes from the fact that most of the lines your program is looking at are absolutely ridiculous. 
		 * Now, if we could only get rid of these ridiculous lines and look at the important ones instead... 
		 * One very general pruning technique that is nearly guaranteed to work in most games is Michael Buro's ProbCut algorithm (and variants thereof): 
		 * In ProbCut, you decide to search less deeply at some fixed remaining depth, 
		 * e.g. when there are 8 ply remaining. Instead, you decide to search only 4 ply. 
		 * Now, if this search returns a value far outside of your alpha-beta window you decide to believe the shallow search and return the result. 
		 * If it's not too far outside of the alpha-beta window, or even inside it, you have to re-search to the full depth. 
		 * There are a lot of constants you can tune in this algorithm, and you will have to experiment with it to get it up to full strength. 
		 * It was used by Buro himself in his world-class Othello program Logistello, and I once implemented a version of Multi-ProbCut in my checkers program Cake. 
		 * It worked much better than plain alphabeta, but not as well as my game-specific pruning algorithm. 
		 * Nevertheless, ProbCut is highly interesting since it doesn't depend on the game you are playing. 
		 * To me it's no surprise that it is outperformed by reduction algorithms which know something about the game - after all, 
		 * these have some knowledge advantage! 
		 */		
		public function DR():void{}
		
		
		
		
		
		
		
		
		private var _alpha:int = 1;
		private var _beta:int = -1;
		private var _depth:int;
			
		public function set alpha(value:int):void
		{
			_alpha = value;
		}
		/**
		 * @param value
		 * @default 1
		 */	
		public function get alpha():int
		{
			return _alpha;
		}
		
		public function set beta(value:int):void
		{
			_beta = value;
		}
		/**
		 * 
		 * @param value
		 * @default -1
		 */	
		public function get beta():int
		{
			return _beta;
		}
		
		public function set depth(value:int):void
		{
			_depth = value;
		}
		/**
		 * 
		 * @param value
		 */	
		public function get depth():int
		{
			return _depth;
		}
	}
}

